package main.leetcode.clockin.June;

/**
 * 209. 长度最小的子数组
 *
 * <p>给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组，并返回其长度。如果不存在符合条件的连续子数组，返回 0。
 *
 * <p>示例: 输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2 解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
 *
 * <p>进阶: 如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
 */
public class day28 {
    public static void main(String[] args) {
        //        System.out.println(new day28().minSubArrayLen(7, new int[] {2, 3, 1, 2, 4, 3}));
        //        System.out.println(new day28().minSubArrayLen(11, new int[] {1, 2, 3, 4, 5}));
        System.out.println(new day28().minSubArrayLen(11, new int[] {10}));
    }
    /** O(n) */
    public int minSubArrayLen1(int s, int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int l = 0;
        int r = 0;
        int sum = 0;
        int res = Integer.MAX_VALUE;
        //        while (true) {
        //            if (sum < s) {
        //                if (r > nums.length - 1) {
        //                    break;
        //                }
        //                sum += nums[r++];
        //            } else {
        //                res = Math.min(res, r - l);
        //                sum -= nums[l++];
        //            }
        //        }
        /*优化*/
        while (r < nums.length) {
            sum += nums[r++];
            while (sum >= s) {
                res = Math.min(res, r - l);
                sum -= nums[l++];
            }
        }

        return res == Integer.MAX_VALUE ? 0 : res;
    }

    /** O(n^2) */
    public int minSubArrayLen2(int s, int[] nums) {
        if (nums == null) {
            return 0;
        }
        int sum;
        int res = Integer.MAX_VALUE;
        int n = nums.length;
        for (int i = 0; i < n; ++i) {
            sum = 0;
            for (int j = i; j < n; ++j) {
                sum += nums[j];
                if (sum >= s) {
                    res = Math.min(res, j - i + 1);
                    break;
                }
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    /** 前缀和 +二分查找 O(nlogn) */
    public int minSubArrayLen(int s, int[] nums) {
        if (nums == null) {
            return 0;
        }
        int res = Integer.MAX_VALUE;
        int n = nums.length;
        int[] pre = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            pre[i] = pre[i - 1] + nums[i - 1];
        }
        for (int i = 0; i < n; ++i) {
            int tar = pre[i] + s;
            int mid = binarySearch(pre, tar);
            if (mid < 0) {
                continue;
            }
            if (mid <= n) {
                res = Math.min(res, mid - i);
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    private int binarySearch(int[] pre, int tar) {
        int l = 0, r = pre.length - 1;
        int mid;
        while (l < r) {
            mid = l + (r - l >>> 1);
            if (pre[mid] < tar) {
                l = mid + 1;
            } else {
                r = mid;
            }
        }
        return pre[l] >= tar ? l : -1;
    }
}
